<!--
    NAME: Daniel Yu
    DATE: 04/04/12
    CLASS: CS 143
    LAB: 1
    YEAR/TERM: Y3-T3
-->

<html>
<head><title>Calculator</title></head>
<body>

<h1>Calculator</h1>
(Ver 0.2 4/11/2012 by Daniel Yu)<br />
Type an expression in the following box (e.g., 10.5+20*3/25).
<p>
<form action="calculator.php" method="GET">
<input type="text" name="expr"><input type="submit" value="Calculate">
</form>
</p>
<ul>
<li>Only numbers and +,-,* and / operators are allowed in the expression.
<li>The evaluation follows the standard operator precedence.
<li>The calculator does not support parentheses.
<li>The calculator handles invalid input "gracefully". It does not output PHP error messages.
</ul>
Here are some(but not limit to) reasonable test cases:
<ol>
  <li> A basic arithmetic operation:  3+4*5=23 </li>
  <li> An expression with floating point or negative sign : -3.2+2*4-1/3 = 4.46666666667, 3+-2.1*2 = -1.2 </li>
  <li> Some typos inside operation (e.g. alphabetic letter): Invalid input expression 2d4+1 </li>
</ol>
</body>
</html>

<?php
    function reportMemoryUsage()
    {
        echo "Memory Used: " . memory_get_usage() . " bytes</br></br>";
    }
    // Reports the amount of memory that has been used so far
    
    function reportError($infixExpr)
    {
        echo "ERROR: Invalid input expression => " . $infixExpr . "</br>";
    }
    // Prints the standard error message
    
    function isOperator($readChar)
    {
        switch($readChar)
        {
            case("+"):
            case("-"):
            case("*"):
            case("/"):
            {
                return(true);
            }
            default:
            {
                return(false);
            }
        }
    }
    // Checks if the character read is a valid operator
    
    function checkPrecedence($curOper, $newOper)
    {
        switch($curOper)
        {
            case(""):
            {
                if($newOper == "")
                {
                    return(0);
                }
                else if(($newOper == "+") || ($newOper == "-") || 
                        ($newOper == "*") || ($newOper == "/"))
                {
                    return(1);
                }
                else
                {
                    return(NULL);
                }
            }
            case("+"):
            case("-"):
            {
                if($newOper == "")
                {
                    return(-1);
                }
                else if(($newOper == "+") || ($newOper == "-"))
                {
                    return(0);
                }
                else if(($newOper == "*") || ($newOper == "/"))
                {
                    return(1);
                }
                else
                {
                    return(NULL);
                }
            }
            case("*"):
            case("/"):
            {
                if(($newOper == "") || ($newOper == "+") || 
                   ($newOper == "-"))
                {
                    return(-1);
                }
                else if(($newOper == "*") || ($newOper == "/"))
                {
                    return(0);
                }
                else
                {
                    return(NULL);
                }
            }
            default:
            {
                return(NULL);
            }
        }
    }
    // Compares the precendence values of the current operator to the new 
    // operator.  Returns a negative if the current operator has lower 
    // precedence.  Returns zero if both operators have equal precedence.  
    // Returns positive if the current operator has higher precedence.  
    // Returns NULL if an invalid character is encountered for the 
    // operator.
    
    function infixToPostfix($infix)
    {
        $opStack = array();
        $postfixArray = array();
        $curOper = "";
        $operFlag = true;
        $negativeFlag = false;
        
        $parsedDigit = false;
        $prevOper = "";
        
        $removedWhitespace = false;
        $cursor = 0;
        
        if(($infix[0] != "-") && (ctype_digit($infix[0]) != true))
        {
            // @ERROR: +, *, / or invalid operator found at start of expression
            
            return(NULL);
        }
        
        while(strlen($infix) > 0)
        {
            if(ctype_digit($infix[0]) == true)
            {
                $digitString = "";
                $decimalFlag = false;
                
                // Scan the infix expression for consecutive digits and 
                // decimal points
                while((count($infix) > 0) && (($infix[0] == ".") || 
                      (ctype_digit($infix[0]) == true)))
                {
                    if($infix[0] == ".")
                    {
                        if($decimalFlag == true)
                        {
                            // @ERROR: Multiple instances of decimal 
                            //         points encountered within same 
                            //         constant value
                            
                            return(NULL);
                        }
                        
                        $decimalFlag = true;
                    }
                    
                    $digitString .= $infix[0];
                    $infix = substr($infix, 1);
                }
                
                // Check if the digit string needs to be evaluated as a 
                // double or an integer
                if($decimalFlag == true)
                {
                    // Check if the negative flag was set
                    if($negativeFlag == false)
                    {
                        $postfixArray[] = doubleval($digitString);
                    }
                    else
                    {
                        $postfixArray[] = doubleval($digitString) * -1;
                    }
                }
                else
                {
                    // Check if the negative flag was set
                    if($negativeFlag == false)
                    {
                        $postfixArray[] = intval($digitString);
                    }
                    else
                    {
                        $postfixArray[] = intVal($digitString) * -1;
                    }
                }
                
                $operFlag = false;
                $negativeFlag = false;
                $prevOper = "";
            }
            else if(isOperator($infix[0]) == true)
            {
                if(($prevOper != "") && ($infix[0] != "-"))
                {
                    // @ERROR: Invalid infix operator encountered
                    
                    return(NULL);
                }
                
                if(($infix[0] == "-") && ($operFlag == true) && 
                   ($negativeFlag == false))
                {
                    // The current character is a negative sign with the 
                    // previous character having been an operation with no 
                    // previous encounters with negative signs.
                    
                    $negativeFlag = true;
                    $infix = substr($infix, 1);
                }
                else if(($infix[0] == "-") && ($negativeFlag == true))
                {
                    // @ERROR: Multiple negative sign symbols were 
                    //         encountered
                    
                    return(NULL);
                }
                else
                {
                    $newOper = $infix[0];
                    $precedence = checkPrecedence($curOper, $newOper);
                    
                    if($precedence === NULL)
                    {
                        // @ERROR: Encountered invalid operation character
                        
                        return(NULL);
                    }
                    else if($precedence < 0)
                    {
                        // New operator has a lower precedence than 
                        // current operator
                        
                        $postfixArray[] = $curOper;
                        
                        while(count($opStack) > 0)
                        {
                            $postfixArray[] = array_pop($opStack);
                        }
                        
                        $curOper = $newOper;
                    }
                    else if($precedence == 0)
                    {
                        // New operator has equal precedence to current 
                        // operator
                        
                        $postfixArray[] = $curOper;
                        $curOper = $newOper;
                    }
                    else if($precedence > 0)
                    {
                        // New operator has greater precedence than 
                        // current operator
                        
                        if($curOper != "")
                        {
                            array_push($opStack, $curOper);
                        }
                        
                        $curOper = $newOper;
                    }
                    
                    $operFlag = true;
                    $infix = substr($infix, 1);
                }
                
                $prevOper = $curOper;
            }
            else if($infix[0] == " ")
            {
                $infix = substr($infix, 1);
            }
            else
            {
                // @ERROR: Encountered invalid character
                
                return(NULL);
            }
        }
        
        if($curOper != "")
        {
            $postfixArray[] = $curOper;
        }
        
        while(count($opStack) > 0)
        {
            $postfixArray[] = array_pop($opStack);
        }
        
        return($postfixArray);
    }
    // Converts an infix string expression into a postfix stack.  Returns 
    // NULL if the conversion was unsuccessful.
    
    function evaluatePostfix(&$postfixArray)
    {
        $numberStack = array();
        
        // Check if all the elements in the postfix array have been 
        // processed
        while(count($postfixArray) > 0)
        {
            $postfixElement = array_shift($postfixArray);
            
            if(is_numeric($postfixElement) == true)
            {
                // The extracted postfix element is a number
                
                array_push($numberStack, $postfixElement);
            }
            else if(isOperator($postfixElement) == true)
            {
                // The extracted postfix element is an operator
                
                switch($postfixElement)
                {
                    case("+"):
                    {
                        $operand1 = array_pop($numberStack);
                        $operand2 = array_pop($numberStack);
                        $value = $operand2 + $operand1;
                        
                        array_push($numberStack, $value);
                        break;
                    }
                    case("-"):
                    {
                        $operand1 = array_pop($numberStack);
                        $operand2 = array_pop($numberStack);
                        $value = $operand2 - $operand1;
                        
                        array_push($numberStack, $value);
                        break;
                    }
                    case("*"):
                    {
                        $operand1 = array_pop($numberStack);
                        $operand2 = array_pop($numberStack);
                        $value = $operand2 * $operand1;
                        
                        array_push($numberStack, $value);
                        break;
                    }
                    case("/"):
                    {
                        $operand1 = array_pop($numberStack);
                        $operand2 = array_pop($numberStack);
                        
                        if($operand1 == 0)
                        {
                            // @ERROR: Divide-by-zero encountered
                            return(NULL);
                        }
                        
                        $value = $operand2 / $operand1;
                        
                        array_push($numberStack, $value);
                        break;
                    }
                    default:
                    {
                        // @ERROR: Invalid operator encountered
                        
                        return(NULL);
                    }
                }
            }
            else
            {
                // @ERROR: The extracted postfix element is an invalid 
                //         character
                
                return(NULL);
            }
        }
        
        $value = array_pop($numberStack);
        
        if(count($numberStack) != 0)
        {
            // @ERROR: The number stack is not empty
            echo count($numberStack);
            return(NULL);
        }
        
        return($value);
    }
    // Evaluates a postfix array to its numeric value.  Returns NULL if 
    // unsuccessful.
    
    function outputValue($infix, $value)
    {
        echo "<h1><b>Result</b></br></h1>";
        echo $infix . " = " . $value;
    }
    // Outputs a value as the result

    function main()
    {
        // Error Reporting Settings
        /*
        error_reporting(E_ALL);
        ini_set("display_errors", "1");
        */
        
        $infix = trim($_GET["expr"]);
        
        if($infix != "")
        {
            $postfixArray = infixToPostfix($infix);
            
            if($postfixArray == NULL)
            {
                // @ERROR: The infix expression provided was not valid
                
                reportError($infix);
                return(-1);
            }
            
            $exprValue = evaluatePostfix($postfixArray);
            
            if($exprValue === NULL)
            {
                // @ERROR: The postfix array could not be evaluated
                
                reportError($infix);
                return(-1);
            }
            
            outputValue($infix, $exprValue);
        }
        
        return(0);
    }
    
    // 'main' function invocation
    main();
?>
